package com.maptasksolver.struct.graph;

import java.io.File;
import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

import com.maptasksolver.exceptions.EdgesCountLimitExceeded;
import com.maptasksolver.exceptions.EmptyTreeException;
import com.maptasksolver.exceptions.NodesCountLimitExceeded;
import com.maptasksolver.exceptions.WrongEdgeNumberSelected;
import com.maptasksolver.exceptions.WrongGraphParamsSelected;
import com.maptasksolver.exceptions.WrongParameter;
import com.maptasksolver.struct.heap.EdgeForHeap;
import com.maptasksolver.struct.heap.Heap;

public class Graph {
	
	// maximal edge count
	private int edges = 0;
	// maximal vertexes count
	private int vertexes = 0;
	// current edge count
	private int edgeCount = 0;
	// arrays for edges list
	private int[] from, where, first, next, last, pathNum;
	private double[] weight;	
	
	private boolean[] visited;
	
	public int[] fromDij;
	
	public static Graph readGraph(String filePath) throws FileNotFoundException, 
		WrongGraphParamsSelected, EdgesCountLimitExceeded {
	
		Scanner scan = new Scanner(new File(filePath));
		
		int edges = scan.nextInt(), vertexes = scan.nextInt();
		
		Graph g = new Graph(edges, vertexes);
		
		for (int i = 0; i < edges; ++i) {
			int from = scan.nextInt(), where = scan.nextInt();
			double weight = scan.nextDouble();
			int pathNum = scan.nextInt();
			
			g.addEdge(from, where, weight, pathNum);
		}		
	
		scan.close();
		return g;		
	}
	
	public static String generateGraph(String filename, int edges, int vertexes) throws FileNotFoundException {
		PrintWriter file = new PrintWriter(new File(filename));
		
		file.write(edges + " " + vertexes + "\n");
		for (int i = 0; i < edges; ++i) {
			int first = (int)((vertexes - 1) * Math.random()) + 1, second = (int)((vertexes - 1) * Math.random()) + 1;
			file.printf("%d %d %.2f %d\n", first, second, Math.random() * 100, 1);
		}	
		
		file.close();
		return filename;
	}	

	public static Graph readGraph(String filePath, int edgesMax) throws FileNotFoundException, 
		WrongGraphParamsSelected, EdgesCountLimitExceeded {
		
		Scanner scan = new Scanner(new File(filePath));
		
		int edges = scan.nextInt(), vertexes = scan.nextInt();
		
		Graph g = new Graph(edgesMax, vertexes);
		
		for (int i = 0; i < edges; ++i) {
			int from = scan.nextInt(), where = scan.nextInt();
			double weight = scan.nextDouble();
			int pathNum = scan.nextInt();
			
			g.addEdge(from, where, weight, pathNum);
		}		
		
		scan.close();
		return g;		
	}

	public Graph(int edges, int vertexes) throws WrongGraphParamsSelected {
		
		if (edges < 0 || vertexes < 0) throw new WrongGraphParamsSelected();
		
		this.edges = edges;
		this.vertexes = vertexes;
		
		first = new int[vertexes + 1];
		next = new int[edges + 1];
		last = new int[vertexes + 1];
		
		from = new int[edges + 1];
		where = new int[edges + 1];
		weight = new double[edges + 1];	
		pathNum = new int[edges + 1];
		
		visited = new boolean[vertexes + 1];
		
		fromDij = new int[vertexes + 1];
	}
	
	public void addEdge(int from, int where, double weight, int pathNum) 
			throws WrongGraphParamsSelected, EdgesCountLimitExceeded {
		
		if (from < 1 || from > vertexes ||
			where < 1 || where > vertexes ||
			pathNum < 1 || weight < 0)
			throw new WrongGraphParamsSelected();
		if (edgeCount == edges) throw new EdgesCountLimitExceeded();
		
		++edgeCount;
		
		this.from[edgeCount] = from;
		this.where[edgeCount] = where;
		this.weight[edgeCount] = weight;
		this.pathNum[edgeCount] = pathNum;
		
		if (first[from] == 0) first[from] = edgeCount; 
		if (last[from] != 0) next[last[from]] = edgeCount;
		last[from] = edgeCount;
	}
	
	public double findPathDFS(int from, int where) throws WrongParameter {
		
		if (from < 1 || from > vertexes ||
			where < 1 || where > vertexes)
			throw new WrongParameter();	
		
		if (from == where) return 0;
		double pathFromHere = Double.MAX_VALUE;
		int cur = first[from];
		
		visited[from] = true;
		
		while (cur != 0) {
			if (!visited[this.where[cur]]) {
				double p = findPathDFS(this.where[cur], where);
				if (p + this.weight[cur] < pathFromHere) pathFromHere = p + this.weight[cur];	
			}		
			cur = next[cur];
		} 
		
		visited[from] = false;
		
		return pathFromHere;
	}
	
	public Path findPathDijkstra(int from, int where) throws WrongParameter,
		WrongEdgeNumberSelected, NodesCountLimitExceeded, EmptyTreeException {
		
		if (from < 1 || from > vertexes ||
				where < 1 || where > vertexes)
				throw new WrongParameter();
		
		visited[from] = true;
		
		double[] dist = new double[vertexes + 1];
		for (int i = 0; i <= vertexes; ++i) dist[i] = Double.MAX_VALUE;
		dist[from] = 0;
		
		Heap heap = new Heap(this.edges);
		
		addToHeap(heap, from, dist);
		int ind = 0;
		while (!heap.isEmpty()) {
			EdgeForHeap e = (EdgeForHeap) heap.pop();
			ind = e.getWhere();
			if (!visited[ind]) {
				visited[ind] = true;
				dist[ind] = dist[e.getFrom()] + e.getWeight();
				addToHeap(heap, ind, dist);
			}				
		}
		
		List<Integer> pathFinal = new ArrayList<Integer>(); 
		
		int dest = where;
		while (dest != 0) {
			pathFinal.add(dest);
			dest = fromDij[dest];
		}
		
		return new Path(pathFinal, dist[where]);
	}
	
	public Edge getEdge(int i) throws WrongEdgeNumberSelected {
		if (i < 0 || i > this.edgeCount) throw new WrongEdgeNumberSelected();
		return new Edge(from[i], where[i], weight[i], pathNum[i]);
	}
	
	public int getVertexes() {
		return vertexes;
	}
	
	public int getEdgeCount() {
		return edgeCount;		
	}
	
	public int getEdges() {
		return edges;
	}
	
	private void addToHeap(Heap heap, int i, double[] dist) throws WrongParameter, 
		NodesCountLimitExceeded, WrongEdgeNumberSelected {
		int cur = first[i];
		while (cur != 0) {
			if (!visited[where[cur]]) {
				if (dist[where[cur]] > dist[from[cur]] + weight[cur]) {
					dist[where[cur]] = dist[from[cur]] + weight[cur];
					heap.add(new EdgeForHeap(getEdge(cur), dist[from[cur]] + weight[cur]));
					
					fromDij[where[cur]] = from[cur];
				}
			}
			cur = next[cur];
		}
	}
	
}
